// 给定一组字符，使用原地算法将其压缩。

// 压缩后的长度必须始终小于或等于原数组长度。

// 数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。

// 在完成原地修改输入数组后，返回数组的新长度。

 

// 进阶：
// 你能否仅使用O(1) 空间解决问题？

 

// 示例 1：

// 输入：
// ["a","a","b","b","c","c","c"]

// 输出：
// 返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]

// 说明：
// "aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
// 示例 2：

// 输入：
// ["a"]

// 输出：
// 返回1，输入数组的前1个字符应该是：["a"]

// 说明：
// 没有任何字符串被替代。
// 示例 3：

// 输入：
// ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

// 输出：
// 返回4，输入数组的前4个字符应该是：["a","b","1","2"]。

// 说明：
// 由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
// 注意每个数字在数组中都有它自己的位置。
// 注意：

// 所有字符都有一个ASCII值在[35, 126]区间内。
// 1 <= len(chars) <= 1000。

#include "../stdc++.h"

// 双指针
class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size();
        int res{0}; // res记录的是当前修改的下标
        for (int i{0}, j{0}; i < n; i = j) {
            while (j < n && chars[j] == chars[i]) // i是第一个字母，j向后遍历直到不同的字母
                ++j;
            chars[res++] = chars[i];
            if (j - i == 1) continue;
            for (char c : to_string(j - i)) // 将 j - i 的值转换为字符串
                chars[res++] = c;
        }
        return res;
    }
};

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size();
        int res{0};
        int left{0};
        int right{0};
        for (; left < n; left = right) {
            while (right < n && chars[left] == chars[right]) {
                ++right;
            }
            chars[res++] = chars[left];
            if (right - left == 1) {
                continue;
            }
            for (char c : to_string(right - left)) {
                chars[res++] = c;
            }
        }
        return res;
    }
};

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size();
        int write = 0, left = 0;
        for (int read = 0; read < n; read++) {
            if (read == n - 1 || chars[read] != chars[read + 1]) {
                chars[write++] = chars[read];
                int num = read - left + 1;
                if (num > 1) {
                    int anchor = write;
                    while (num > 0) {
                        chars[write++] = num % 10 + '0';
                        num /= 10;
                    }
                    reverse(&chars[anchor], &chars[write]);
                }
                left = read + 1;
            }
        }
        return write;
    }
};

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size();
        int res{0};
        int left{0};
        int right{0};
        for (; left < n; left = right) {
            while (right < n && chars[left] == chars[right]) {
                ++right;
            }
            chars[res++] = chars[left];
            int len = right - left;
            if (len > 1) {
                int anchor = res;
                while (len > 0) {
                    chars[res++] = '0' + len % 10;
                    len /= 10;
                }
                reverse(&chars[anchor], &chars[res]);
            }
        }
        return res;
    }
};
